"""
Q5 最长回回文串
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案
"""

def solution(s):
    begin= 0
    max_len = 0
    length = len(s)
    dp = [[False]*length for _ in range(length)]
    for i in range(length):
        dp[i][i] = True
    if length <2:
        return s
    for left in range(2,length+1):
        for i in range(length):
            right = left + i -1
            if right >length:
                break
            if s[right] !=s[i]:
                dp[i][right]=False
            else:
                if right-i < 3:
                    dp[i][right]=True
                else:
                    dp[i][right]=dp[i+1][right-1]

            if dp[i][right] == True and (right - i >max_len):
                max_len = right -i
                begin = i
    return s[begin:max_len]


